// C-style linked lists
// By Paril

// DL = doubly linked
// SL = singly/linearly linked

struct SLNode_t
{
	void					*data;
	SLNode_t				*next;
};

struct SLList_t
{
	SLNode_t				*head, *tail;
	int						count;
};

// Forward declarations
inline void sllist_init (SLList_t *list);
inline void sllist_delete (SLList_t *list);
inline void sllist_add (SLList_t *list, void *data);
inline void sllist_remove (SLList_t *list, void *data);
inline void sllist_remove (SLList_t *list, SLNode_t *node);
inline void sllist_clear (SLList_t *list);

// Implementations
inline void sllist_init (SLList_t *list)
{
	list->count = 0;
	list->head = list->tail = NULL;
}

inline void sllist_add (SLList_t *list, void *data)
{
	list->count++;

	SLNode_t *newNode = new SLNode_t;
	newNode->data = data;
	newNode->next = NULL;

	if (list->tail == NULL)
		list->tail = list->head = newNode;
	else
	{
		list->tail->next = newNode;
		list->tail = newNode;
	}
}

inline void sllist_remove (SLList_t *list, void *data)
{
	list->count--;

	SLNode_t *prevNode = NULL, *node = list->head;

	for (; node != NULL; node = node->next)
	{
		if (node->next != NULL && node->next->data == data)
			prevNode = node;
		else if (node->data == data)
			break;
	}

	if (prevNode != NULL)
		prevNode->next = node->next;

	if (list->head == node)
		list->head = node->next;
	if (list->tail == node)
		list->tail = prevNode;

	delete node;
}

inline void sllist_remove (SLList_t *list, SLNode_t *node)
{
	sllist_remove (list, node->data);
}

inline void sllist_clear (SLList_t *list)
{
	SLNode_t *node = list->head;

	while (node != NULL)
	{
		SLNode_t *next = node->next;

		delete node;
		node = next;
	}

	list->count = 0;
	list->head = list->tail = NULL;
}

inline void sllist_delete (SLList_t *list)
{
	list->count = 0;
	sllist_clear(list);
}





struct DLNode_t
{
	void					*data;
	DLNode_t				*next, *prev;
};

struct DLList_t
{
	DLNode_t				*head, *tail;
	int						count;
};

// Forward declarations
inline void dllist_init (DLList_t *list);
inline void dllist_delete (DLList_t *list);
inline void dllist_add (DLList_t *list, void *data);
inline void dllist_remove (DLList_t *list, void *data);
inline void dllist_remove (DLList_t *list, DLNode_t *node);
inline void dllist_clear (DLList_t *list);
inline bool dllist_contains (DLList_t *list, DLNode_t *node);
inline void dllist_insert (DLList_t *list, DLNode_t *node, void *data);

// Implementations
inline void dllist_init (DLList_t *list)
{
	list->count = 0;
	list->head = list->tail = NULL;
}

inline void dllist_add (DLList_t *list, void *data)
{
	list->count++;

	DLNode_t *newNode = new DLNode_t;
	newNode->data = data;
	newNode->next = newNode->prev = NULL;

	if (list->tail == NULL)
		list->tail = list->head = newNode;
	else
	{
		list->tail->next = newNode;
		newNode->prev = list->tail;
		list->tail = newNode;
	}
}

inline void dllist_remove (DLList_t *list, void *data)
{
	list->count--;

	DLNode_t *node = list->head;

	for (; node != NULL; node = node->next)
	{
		if (node->data == data)
			break;
	}

	if (node->prev != NULL)
		node->prev->next = node->next;
	if (node->next != NULL)
		node->next->prev = node->prev;

	if (list->head == node)
	{
		list->head = node->next;

		if (list->head != NULL)
			list->head->prev = NULL;
	}
	if (list->tail == node)
	{
		list->tail = node->prev;

		if (list->tail != NULL)
			list->tail->next = NULL;
	}

	delete node;
}

inline void dllist_insert (DLList_t *list, DLNode_t *node, void *data)
{
	if (node == NULL)
	{
		dllist_add (list, node);
		return;
	}

	list->count++;

	DLNode_t *newNode = new DLNode_t;
	newNode->data = data;
	newNode->next = newNode->prev = NULL;

	// slip node in-between
	newNode->prev = node->prev;
	newNode->next = node;

	if (node->prev != NULL)
		node->prev->next = newNode;
	else
		list->head = newNode;

	if (newNode->next != NULL)
		newNode->next->prev = newNode;
	else
		list->tail = newNode;
}

inline void dllist_remove (DLList_t *list, DLNode_t *node)
{
	dllist_remove (list, node->data);
}

inline void dllist_clear (DLList_t *list)
{
	DLNode_t *node = list->head;

	while (node != NULL)
	{
		DLNode_t *next = node->next;

		delete node;
		node = next;
	}

	list->count = 0;
	list->head = list->tail = NULL;
}

inline void dllist_delete (DLList_t *list)
{
	list->count = 0;
	dllist_clear(list);
}

inline bool dllist_contains (DLList_t *list, void *data)
{
	for (DLNode_t *node = list->head; node != NULL; node = node->next)
		if (node->data == data)
			return true;

	return false;
}